package com.MSB2.sort1;

/**
 * 归并排序
 * LeetCode 327.区间和的个数
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {3, 6, 4, 2, 45, 2, 3, 54, 6, 546, 4, 90};
        mergeSorted(arr);
        for (int j : arr) {
            System.out.println(j);
        }
    }

    /**
     * 非递归实现
     * @param arr
     */
    public static void mergeSorted(int[] arr){
        if (arr == null || arr.length <= 1)
            return;
        int n = arr.length;
        int step = 1;
        while (step < n){
            int L = 0;
            while (L < n){
                int m = L + step - 1;
                if (m >= n)
                    break;
                int R = Math.min(m + step, n - 1);
                merge(arr, L, m, R);
                L = R + 1;
            }
            step = step << 1;
        }
    }

    /**
     * 递归实现
     * @param arr
     */
    public static void mergeSortRecursion(int[] arr){
        process(arr,0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R){
        if (L == R)
            return;
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    /**
     * 合并两个排好序的数组
     * @param arr 数组
     * @param l 左
     * @param mid 中
     * @param r 右
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, l, help.length);
    }
}
